剑指 Offer 59. xx的最大值

连做两道队列的题，根本思想是一样的，找到最大值的方法就是维护一个有序队列，使用双指针deque容器。算法有点意思。

I 滑动窗口的最大值

题目表述

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

优先队列

维护一个最大优先队列(堆)，堆顶就是当前队列的最大值，出队出最大值
使用pair方式存放当前值和其位置

初始化滑动窗，存放k个元素到队列，存放当前最大值到最大优先队列，插入第一个最大值到容器中。
插入第k+1个数值，同时应排出第一个数值，在剩下数值中寻找最大值。根据位置（pair.second），找到应该在窗里的最大优先队列维护的最大值（循环，pop索引小于窗的值）
将当前最大值插入回答容器中。

时间复杂度：
O(nlogn)，其中 n 是数组nums 的长度。在最坏情况下，数组 nums中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)。
空间复杂度
O(n)，优先队列所需使用的空间。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        priority_queue<pair<int,int>> q;
        vector<int> ans;

        // 初始化队列
        for (int i = 0;i<k;i++){
            q.emplace(nums[i],i);
        }
        ans.push_back(q.top().first);

        for(int i = k; i<nums.size(); i++){
            // 插入数据
            q.emplace(nums[i],i);

            // 找到应在窗内的最大值
            while(q.top().second<=i-k){ // 不应该出现在维护窗里的数
                q.pop(); //删除
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

单调队列

使用队列存放最大值，维护一个单调递减的队列。
每次最大值放入单调队列，有更大值时排出并重放，保证单调递减
最后根据窗的位置确定最大值范围，超过范围的最大值不使用。

时间复杂度
O(n)，n 是数组nums 的长度.
空间复杂度
双向有序队列，不超过k+1个元素，O(k).

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
         vector<int> ans；
        deque<int> q;
        // 初始化
        for (int i = 0; i < k; ++i) {
            // 找到当前窗中的最大值存放，只存放一个值
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            // 当 当前值比单调队列中的值都小
            q.push_back(i);
        }
        ans.push_back(nums[q.front()]);

        // 后续节点
        for (int i = k; i < nums.size(); ++i) {
            // 找到比当前值大的值
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);

            // 弹出不在队列中的最大值，维护单调队列
            while (q.front() <= i - k) {
                q.pop_front();
            }
            // 将当前窗中的最大值放到ans中
            ans.push_back(nums[q.front()]);
        }

        return ans;
    }
};

II 队列的最大值

题目表述

请定义一个队列并实现函数 max_value 得到队列里的最大值，
要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

解题思路

维护一个单调的双端队列
使用队列存放要求数据，使用单调双端队列表示当前最大值，该最大值不与队列一一对应，
当维护的双端队列与插入新的值时比较，如果插入值较大意味着在该数值出队前，队列最大值都是该值，即取出当前双端队列所有小于的值，输入当前值；
如果插入值小于当前值，则将当前值放入双端队列中，因为索引到当前值时意味着之前的值都已经出栈了
这样维护，实现一个单调递减的双端队列。

代码

class MaxQueue {
private:
    queue<int> q;
    deque<int> d;

public:
    MaxQueue() {

    }
    
    int max_value() {
        if(d.empty()) return -1;
        return d.front();
    }
    
    void push_back(int value) {
        while(!d.empty()&&d.back()<value){
            d.pop_back();
        }
        d.push_back(value);
        q.push(value);
    }
    
    int pop_front() {
        if(q.empty()) return -1;

        int ans = q.front();
        if(ans==d.front()){
            d.pop_front();
        }
        q.pop();
        return ans;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

Duder's Blog